﻿//1011. 在 D 天内送达包裹的能力
//传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
//传送带上的第 i 个包裹的重量为 weights[i]。
//每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
//返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。


class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days)
    {
        auto check = [&](long long w)->bool
        {
            int day = 0;
            int i = 0;
            while (i < weights.size())
            {
                long long sum = 0;
                while (i < weights.size() && sum + weights[i] <= w)
                {
                    sum += weights[i];
                    i++;
                }
                day++;
            }
            return day <= days;
        };
        long long max_w = ranges::max(weights);
        long long sum_w = accumulate(weights.begin(), weights.end(), 0);
        long long left = max_w, right = sum_w;
        while (left <= right)
        {
            long long mid = (left + right) / 2;
            if (check(mid))
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return right + 1;
    }
};